package com.msb;

/**
 * @author whf
 * @date 2024-12-16 18:08
 */

// 测试链接：https://leetcode.com/problems/reverse-nodes-in-k-group/
public class _10_hard链表范围内倒序 {

    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    // 1.边界条件
    // 2.第一次反序记末尾节点作为最终返回
    // 3.循环反序, 反序后末尾节点注意和上一个相连)
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (k <= 1) {
            return head;
        }
        ListNode kGroupEnd = getKGroupEnd(head, k);
        if (kGroupEnd == null) {
            return head;
        }
        reverse(head, kGroupEnd);
        ListNode lastEnd = head;
        ListNode next = head.next;
        ListNode kGroupEnd2 = getKGroupEnd(next, k);
        while (kGroupEnd2 != null) {
            reverse(next, kGroupEnd2);
            lastEnd.next = kGroupEnd2;
            lastEnd = next;
            next = next.next;
            kGroupEnd2 = getKGroupEnd(next, k);
        }
        return kGroupEnd;
    }

    // 从当前节点往后数k个位置, 当前为第1个位置
    public static ListNode getKGroupEnd(ListNode start, int k) {
        for (; k > 1 && start != null; k--) {
            start = start.next;
        }
        return start;
    }

    // 开始节点到结束节点倒序, 并且开始节点指向结尾的下一个节点
    public static void reverse(ListNode start, ListNode end) {
        end = end.next;
        ListNode pre = null;
        ListNode current =  start;
        ListNode next = null;
        while (current != end) {
            next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        start.next = end;
    }

}
